import collections


class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        size = len(A)

        change = [[] for _ in range(6)]

        differ = 0

        for i in range(size):
            if A[i] != B[i]:
                change[ord(A[i]) - 97].append(ord(B[i]) - 97)
                differ += 1

        print(change)

        ans = 0

        while differ > 0:
            line = []

            # 寻找所有可以作为开头的结点
            queue = collections.deque()
            for i in range(6):
                if change[i]:
                    queue.append([i])

            # 寻找最短转回的路径
            while queue:
                for _ in range(len(queue)):
                    lst = queue.popleft()
                    if lst[0] in change[lst[-1]]:
                        line = lst
                        break
                    else:
                        for j in change[lst[-1]]:
                            if j not in lst:
                                queue.append(lst + [j])
                if line:
                    break

            differ -= len(line)
            for j in range(len(line) - 1):
                change[line[j]].remove(line[j + 1])
            change[line[-1]].remove(line[0])

            print(line, change)

            ans += len(line) - 1

        return ans


if __name__ == "__main__":
    print(Solution().kSimilarity(A="ab", B="ba"))  # 1
    print(Solution().kSimilarity(A="abc", B="bca"))  # 2
    print(Solution().kSimilarity(A="abac", B="baca"))  # 2
    print(Solution().kSimilarity(A="aabc", B="abca"))  # 2

    # 测试用例47/57
    print(Solution().kSimilarity("aabbccddee", "cdacbeebad"))  # 6

    # 测试用例55/57
    print(Solution().kSimilarity("abcdefabcdefabcdef",
                                 "edcfbebceafcfdabad"))  # 10
